package 高效制胜._08;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/16 8:59
 * 词典中最长的单词
 * 算法：字典树  哈希表
 * 将所有单词放入字典树中
 * 节点的 idx：
 *  1、判断以这个字符结尾的单词是否存在；
 *  2、如果存在，就根据 idx 去 words 找相应的单词
 */
public class _720 {

    public String longestWord(String[] words) {
        Trie trie = new Trie();
        trie.words = words;
        for (int i = 0; i < words.length; i++) trie.insert(words[i], i);
        return trie.dfs();
    }
    class Trie {
        class Node {
            char c;
            int idx = -1;
            Map<Character, Node> children = new HashMap<>();
            Node(char c) {
                this.c = c;
            }
        }
        Node root;
        String[] words;
        Trie() {
            root = new Node('0');
        }
        void insert(String word, int idx) {
            Node cur = root;
            for (char c : word.toCharArray()) {
                cur.children.putIfAbsent(c, new Node(c));
                cur = cur.children.get(c);
            }
            cur.idx = idx;
        }
        String dfs() {
            Deque<Node> stack = new LinkedList<>();
            stack.push(root);
            String ans = "";
            while (!stack.isEmpty()) {
                final Node node = stack.pop();
                if (node.idx != -1 || node == root) {
                    if (node != root) {
                        String word = words[node.idx];
                        if (word.length() > ans.length() ||
                        word.length() == ans.length() && word.compareToIgnoreCase(ans) < 0) ans = word;
                    }
                    for (Node value : node.children.values()) stack.push(value);
                }
            }
            return ans;
        }
    }

}
